package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.DfsCycleCheck;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.DfsOrder;
import lombok.AccessLevel;
import lombok.Getter;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * <h1>数据结构 图</h1>
 * <p>
 *     使用邻接表表示的图结构.内部用的都是{@link Map}、{@link List}等容器。主要是体现图的相关算法的思想。
 *     <br>
 *     追求效率的话，一般使用int数据来实现。
 * </p>
 * @author longandai@163.com
 */
public class Graph<T> {
    /**
     * 是否是有向图
     */
    @Setter(AccessLevel.PRIVATE)
    @Accessors(chain = true)
    private boolean directed;


    /**
     * 链表+hashset
     */
    @Getter
    private LinkedHashMap<Vertex<T>,Vertex<T>> vertices = new LinkedHashMap<>();
    @Getter
    private Algrithm algrithm = new Algrithm();


    /**
     * 获取所有顶点信息
     * @return
     */
    public List<Vertex<T>> listVertex() {
        return this.vertices.entrySet().stream().map(Map.Entry::getValue).collect(Collectors.toList());
    }










    /**
     * <h2>增加顶点<h2/>
     * <p>增加一个顶点信息。如果顶点之前存在，则覆盖掉。</p>
     * @param vertex
     * @return
     */
    public Graph<T> add(Vertex<T> vertex){
        vertices.put(vertex,vertex);
        return this;
    }
    /**
     * <h2>增加顶点<h2/>
     * <p>增加一个顶点信息。如果顶点之前存在，则覆盖掉。</p>
     * @param key
     * @return
     */
    public Graph<T> add(T key){
        return this.add(Vertex.create(key));
    }
    /**
     * <h2>增加顶点关系<h2/>
     * <p>顶点如果不存在，则增加顶点信息；如果顶点存在，获取顶点信息，增加上关系</p>
     * @param from
     * @param to
     * @return
     */
    public Graph<T> add(Vertex<T> from, Vertex<T> to,double weight) {
        //不允许自身连通
        if(Objects.equals(from,to)){
            return this;
        }
        from = this.addIfNotExists(from);
        to = this.addIfNotExists(to);
        from.addEdge(Edge.create(from,to,weight));
        //无向图需要维护两方关系
        if(!directed){
            to.addEdge(Edge.create(to,from,weight));
        }
        return this;
    }
    /**
     * <h2>增加顶点关系<h2/>
     * <p>顶点如果不存在，则增加顶点信息；如果顶点存在，获取顶点信息，增加上关系</p>
     * @param from
     * @param to
     * @return
     */
    public Graph<T> add(T from, T to,double weight) {
        return this.add(Vertex.create(from),Vertex.create(to),weight);
    }
    /**
     * <h2>增加顶点关系<h2/>
     * <p>顶点如果不存在，则增加顶点信息；如果顶点存在，获取顶点信息，增加上关系</p>
     * @param from
     * @param to
     * @return
     */
    public Graph<T> add(Vertex<T> from, Vertex<T> to) {
        return add(from,to,1.0d);
    }
    /**
     * <h2>增加顶点关系<h2/>
     * <p>顶点如果不存在，则增加顶点信息；如果顶点存在，获取顶点信息，增加上关系</p>
     * @param from
     * @param to
     * @return
     */
    public Graph<T> add(T from, T to) {
        return add(from,to,1.0d);
    }


    /**
     * 如果{@code vertices}中不存在，则增加并返回<br>
     * 如果{@code vertices}存在，则返回现有列表中的信息<br>
     * @param vertex
     * @return
     */
    private Vertex<T> addIfNotExists(Vertex<T> vertex) {
        if(this.vertices.containsKey(vertex)){
            return vertices.get(vertex);
        }else {
            this.add(vertex);
            return vertex;
        }
    }

    /**
     * 按照每个节点，展示节点信息及节点信息的邻接列表
     *
     * 遍历所有顶点信息key->[(key1,weight),(..),(..),]
     * @return
     */
    public String log(boolean withWeight){


       return this.vertices.keySet().stream().map(vertex -> {
          String edgInfo
           =  vertex.getNext()
                   .stream()
                   .map(edge -> withWeight?"("+edge.getTo().getKey().toString()+","+edge.getWeight()+")":edge.getTo().getKey().toString())
                  .collect(Collectors.joining(","));

           return vertex.getKey() + "->" + "[" + edgInfo + "]";

        }).collect(Collectors.joining("\n"));
    }

    /**
     * <h2>取反操作</h2>
     * <p>
     *     取反图可以迅速找出指向顶点的边。
     * </p>
     * @return
     */
    public Graph<T> reverse(){
        if(!this.directed){
            throw new UnsupportedOperationException("无向图取反没有意义");
        }

        Graph<T> reverseG = new Graph<T>().setDirected(true);

        this.getVertices().forEach((key,value)->{
            reverseG.add(value.getKey());
            if(value.getNext()!=null){
                value.getNext().forEach(next->{
                    reverseG.add(next.getTo().getKey(), value.getKey());
                });
            }

        });

        return reverseG;

    }

    /**
     * 是否是有向无环图
     * @return
     */
    public boolean isDag(){
        return directed && !DfsCycleCheck.create(this).isHasCycle();
    }

    /**
     * <h1>拓扑排序</h1>
     * <pre>
     *     ，解决任务调度类 应用通常需要以下 3 步： 
     *     指明任务和优先级条件； 
     *     不断检测并去除有向图中的所有环，以 确保存在可行方案的； 
     *     使用拓扑排序解决调度问题
     * </pre>
     * <pre>
     *      命题 F。一幅有向无环图的拓扑顺序即为所有顶点的逆后序排列。
     *      证明。对于任意边 v → w，在调用 dfs(v) 时，下面三种情况必有其一成立（请见图 4.2.11）。
     * 	        1 dfs(w) 已经被调用过且已经返回了（w 已经被标记）。
     * 	        2 dfs(w) 还没有被调用（w 还未被标记），因此 v → w 会直接或间接调用并返回 dfs(w)，且 dfs(w) 会在 dfs(v) 返回前返回。
     * 	        3 dfs(w) 已经被调用但还未返回。证明的关键在于，在有向无环图中这种情况是不可能出 现的，这是由于递归调用链意味着存在从w到v的路径，但存在v→w则表示存在一个环。
     *      在两种可能的情况中，dfs(w) 都会在 dfs(v) 之前完成，因此在后序排列中 w 排在 v 之前而 在逆后序中w排在v 之后。因此任意一条边v→w都如我们所愿地从排名较前顶点指向排名较后的 顶点。
     * </pre>
     * @return
     */
    public Iterable<Vertex<T>> topological(){
        if(!isDag()){
            throw new UnsupportedOperationException("当前图不是有向无环图");
        }

        return DfsOrder.create(this).getReversePost();
    }

    public static final <T> Graph<T> create(boolean directed){
        return new Graph<T>().setDirected(directed);
    }



    /**
     * 算法
     * @author longandai@163.com
     */
    public  final class Algrithm{
        private Algrithm(){

        }

        /**
         * <h1>深度优先遍历<h1/>
         * <p>
         *     图的深度优先遍历，选择一个顶点，优先按照一条链路向下遍历
         * </p>
         * <p>
         *     思路：类似于树的深度优先遍历，利用栈结构进行遍历，需要维护一个数据集保存已经遍历过的顶点。<br>
         *
         *
         * </p>
         * @param function 返回false中断过程
         */
        public void dfs(Function<T,Boolean> function, T start ){

            Set<Vertex<T>> trim = new HashSet<>();
            Deque<Vertex<T>> deque = new LinkedList();
            deque.push(vertices.get(Vertex.create(start)));
            while(!deque.isEmpty()){

                Vertex<T> item = deque.pop();
                if(!trim.add(item)){
                    continue;
                }
                if (!function.apply(item.getKey())) {
                    return;
                }
                item.getNext()
                        .stream()
                        .map(Edge::getTo)
                        .filter(next->!trim.contains(next))
                        .forEach(deque::push);
            }

        }
        public void dfs( final Consumer<T> consumer,T start ){
            this.dfs(t -> {
                consumer.accept(t);
                return true;
            },start);


        }
        /**
         * <h1>广度优先遍历</h1>
         * <p>
         *     图的广度优先遍历，选择一个顶点，按照广度进行遍历
         * </p>
         * <p>
         *     思路：类似于树的广度优先遍历，利用队列结构进行遍历，需要维护一个数据集保存已经遍历过的顶点。<br>
         *
         *
         * </p>
         * @param consumer
         */
        public void bfs(Consumer<T> consumer,T start ){
            Set<Vertex<T>> trim = new HashSet<>();
            Deque<Vertex<T>> deque = new LinkedList();
            deque.offer(vertices.get(Vertex.create(start)));
            while(!deque.isEmpty()){
                Vertex<T> item = deque.poll();
                if(!trim.add(item)){
                    continue;
                }
                consumer.accept(item.getKey());
                item.getNext()
                        .stream()
                        .map(Edge::getTo)
                        .filter(next->!trim.contains(next))
                        .forEach(deque::offer);
            }
        }

        /**
         * <h1>连通分量<h1/>
         * <p>
         *    不连通的图是由2个或者2个以上的连通子图组成的。这些不相交的连通子图称为图的连通分量。
         * </p>
         * <p>
         *     思路：通过dfs方法。对于无向图来说，一次dfs就可以遍历一个连通分量。
         *     遍历所有顶点，在遍历的同事利用set把dfs遍历到的顶点缓存起来，遍历的时候判断set中有就不在做dfs。这样每个连通分量只会做一次dfs。
         * </p>
         * @return
         */
        public List<List<T>> connectedComponent(){
            Set<T> trim = new HashSet<>();
            List<List<T>> result = new ArrayList<>();

            vertices.keySet().forEach(vertex->{
                if (!trim.add(vertex.getKey())) {
                    return;
                }
                List<T> one = new ArrayList<>();
                dfs(vertexi->{
                    one.add(vertexi);
                    trim.add(vertexi);
                    },vertex.getKey());
                result.add(one);
            });

            return result;
        }

        /**
         * <h1>可达性分析</h1>
         * <p>
         *    查看两个顶点之间是否可达。
         * </p>
         * <p>思路：通过dfs方法。判断在dfs过程中是否碰到target信息。</p>
         */
        public boolean checkLinked(T source,T target){

            AtomicBoolean result = new AtomicBoolean(false);
            dfs(v->{
                if(Objects.equals(v,target)){
                    result.set(true);
                    return false;
                }
                return true;
            },source);
            return result.get();
        }

    }




}
